package org.apache.solr.util;

/** Utilities for primitive Java data types. */
public class PrimUtils {

    public static abstract class IntComparator {

        public abstract int compare(int a, int b);

        public boolean lessThan(int a, int b) {
            return compare(a, b) < 0;
        }

        public boolean equals(int a, int b) {
            return compare(a, b) == 0;
        }
    }

    /**
     * Sort the integer array from "start" inclusive to "end" exclusive in
     * ascending order, using the provided comparator. TODO: is this an unstable
     * sort?
     */
    public static void sort(int start, int end, int[] array, IntComparator comparator) {
        // This code was copied from Apache Harmony's Arrays.sort(double[]) and modified
        // to use a comparator, in addition to other small efficiency enhancements
        // like replacing divisions with shifts.

        int temp;
        int length = end - start;
        if (length < 7) {
            for (int i = start + 1; i < end; i++) {
                for (int j = i; j > start && comparator.lessThan(array[j], array[j - 1]); j--) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
            return;
        }
        int middle = (start + end) >>> 1;
        if (length > 7) {
            int bottom = start;
            int top = end - 1;
            if (length > 40) {
                length >>= 3;
                bottom = med3(array, bottom, bottom + length, bottom + (length << 1), comparator);
                middle = med3(array, middle - length, middle, middle + length, comparator);
                top = med3(array, top - (length << 1), top - length, top, comparator);
            }
            middle = med3(array, bottom, middle, top, comparator);
        }
        int partionValue = array[middle];
        int a, b, c, d;
        a = b = start;
        c = d = end - 1;
        while (true) {
            while (b <= c && !comparator.lessThan(partionValue, array[b])) {
                if (comparator.equals(array[b], partionValue)) {
                    temp = array[a];
                    array[a++] = array[b];
                    array[b] = temp;
                }
                b++;
            }
            while (c >= b && !comparator.lessThan(array[c], partionValue)) {
                if (comparator.equals(array[c], partionValue)) {
                    temp = array[c];
                    array[c] = array[d];
                    array[d--] = temp;
                }
                c--;
            }
            if (b > c) {
                break;
            }
            temp = array[b];
            array[b++] = array[c];
            array[c--] = temp;
        }
        length = a - start < b - a ? a - start : b - a;
        int l = start;
        int h = b - length;
        while (length-- > 0) {
            temp = array[l];
            array[l++] = array[h];
            array[h++] = temp;
        }
        length = d - c < end - 1 - d ? d - c : end - 1 - d;
        l = b;
        h = end - length;
        while (length-- > 0) {
            temp = array[l];
            array[l++] = array[h];
            array[h++] = temp;
        }
        if ((length = b - a) > 0) {
            sort(start, start + length, array, comparator);
        }
        if ((length = d - c) > 0) {
            sort(end - length, end, array, comparator);
        }
    }

    private static int med3(int[] array, int a, int b, int c, IntComparator comparator) {

        int x = array[a], y = array[b], z = array[c];
        return comparator.lessThan(x, y) ? (comparator.lessThan(y, z) ? b : (comparator.lessThan(x, z) ? c : a))
                : (comparator.lessThan(z, y) ? b : (comparator.lessThan(z, x) ? c : a));
    }
}
